package main

// 17. 电话号码的字母组合
func main() {
	nums := "23"
	res := letterCombinations(nums)
	for _, l := range res {
		println(l)
	}
}

var numStrMap = map[string][]string{
	"2": {"a", "b", "c"},
	"3": {"d", "e", "f"},
	"4": {"g", "h", "i"},
	"5": {"j", "k", "l"},
	"6": {"m", "o", "n"},
	"7": {"p", "q", "r", "s"},
	"8": {"t", "u", "v"},
	"9": {"w", "x", "y", "z"},
}

func letterCombinations(digits string) []string {
	var dfs func(arr1, arr2 []string) (combineArr []string)
	dfs = func(arr1, arr2 []string) (combineArr []string) {
		if len(arr1) == 0 {
			return arr2
		} else if len(arr2) == 0 {
			return arr1
		}
		if len(arr1) == 0 && len(arr2) == 0 {
			return []string{}
		}
		for _, item1 := range arr1 {
			for _, item2 := range arr2 {
				combineArr = append(combineArr, item1+item2)
			}
		}
		return combineArr
	}

	var preStrs []string
	for _, char := range digits {
		preStrs = dfs(preStrs, numStrMap[string(char)])
	}

	return preStrs
}

// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
//给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//
//
//
//
//示例 1：
//
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
//示例 2：
//
//输入：digits = ""
//输出：[]
//示例 3：
//
//输入：digits = "2"
//输出：["a","b","c"]
//
//
//提示：
//
//0 <= digits.length <= 4
//digits[i] 是范围 ['2', '9'] 的一个数字。
